﻿using System;
using System.Collections.Generic;

namespace ProblemsSet
{
    public class Problem_57 : BaseProblem
    {
        public override object GetResult()
        {
            const int mx = 1000;

            var nom = new List<string>(mx+1) {"1", "3"};
            var denom = new List<string>(mx+1) {"1", "2"};

            var res = 0;
            long tmp = 0;
            for (var i = 2; i <= mx; i++)
            {
                var q1 = MathLogic.SummString(MathLogic.MultipleString(nom[nom.Count - 1],2, out tmp),nom[nom.Count - 2]);
                var q2 = MathLogic.SummString(MathLogic.MultipleString(denom[denom.Count - 1], 2, out tmp), denom[denom.Count - 2]);
                if (q1.Length> q2.Length)
                {
                    res++;
                }
                nom.Add(q1);
                denom.Add(q2);
            }
            return res;
        }

        public override string Problem
        {
            get
            {
                return @"It is possible to show that the square root of two can be expressed as an infinite continued fraction.

 2 = 1 + 1/(2 + 1/(2 + 1/(2 + ... ))) = 1.414213...

By expanding this for the first four iterations, we get:

1 + 1/2 = 3/2 = 1.5
1 + 1/(2 + 1/2) = 7/5 = 1.4
1 + 1/(2 + 1/(2 + 1/2)) = 17/12 = 1.41666...
1 + 1/(2 + 1/(2 + 1/(2 + 1/2))) = 41/29 = 1.41379...

The next three expansions are 99/70, 239/169, and 577/408, but the eighth expansion, 1393/985, is the first example where the number of digits in the numerator exceeds the number of digits in the denominator.

In the first one-thousand expansions, how many fractions contain a numerator with more digits than denominator?";
            }
        }

        public override bool IsSolved
        {
            get
            {
                return true;
            }
        }

        public override object Answer
        {
            get
            {
                return 153;
            }
        }

    }
}
